#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

vector<int> G[N];

int in[N];

priority_queue< int, vector<int>, greater<int> > q;

struct E {
    int u, v;
    E() {}
    E(int _u, int _v) {
        u = _u;
        v = _v;
    }
}e[N];
int e_tot;

int tp[N], tp_tot;

int main() {
#ifndef __SKT__
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
#endif
    int n, m, k;
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {

        memset(in, 0, sizeof(in));
        e_tot = tp_tot = 0;

        for(int i = 0; i < m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            ++in[v];
        }
        for(int i = 1; i <= n; ++i) {
            if(in[i] == 0) {
                q.push(i);
            }
        }
        while(!q.empty()) {
            while(k > 0 && q.size() >= 2) {
                int now = q.top(); q.pop();
                int nxt = q.top();
                G[nxt].push_back(now);
                e[e_tot++] = E(nxt, now);
                ++in[now];
                --k;
            }
            int now = q.top(); q.pop();
            tp[tp_tot++] = now;
            for(int i = 0; i < G[now].size(); ++i) {
                int nxt = G[now][i];
                --in[nxt];
                if(in[nxt] == 0) {
                    q.push(nxt);
                }
            }
        }
        for(int i = 0; i < n; ++i) {
            printf("%d%c", tp[i], i == n - 1 ? '\n' : ' ');
        }
        printf("%d\n", e_tot);
        for(int i = 0; i < e_tot; ++i) {
            printf("%d %d\n", e[i].u, e[i].v);
        }
    }
    return 0;
}

